// 排序+双指针；时间复杂度O(n^3)；空间复杂度O(logn)

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        for (int a = 0; a < n; a++) {
            for (int b = a + 1; b < n; b++) {
                int c = b + 1, d = n - 1;
                while (c < d) {
                    if (nums[a] + nums[b] == target - nums[c] - nums[d]) {
                        ret.push_back({nums[a], nums[b], nums[c], nums[d]});
                        while (c + 1 < d && nums[c + 1] == nums[c]) {
                            c++;
                        }
                        c++;
                        while (c < d - 1 && nums[d - 1] == nums[d]) {
                            d--;
                        }
                        d--;
                        continue;
                    }
                    if (nums[a] + nums[b] < target - nums[c] - nums[d]) {
                        c++;
                    }
                    if (nums[a] + nums[b] > target - nums[c] - nums[d]) {
                        d--;
                    }
                }
                while (b + 1 < n && nums[b + 1] == nums[b]) {
                    b++;
                }
            }
            while (a + 1 < n && nums[a + 1] == nums[a]) {
                a++;
            }
        }
        return ret;
    }
};